package day2_linkedlist.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 深拷贝带随机指针的链表
 * 使用Map映射巧妙解决此问题
 * @author yuisama
 * @date 2021/12/29 17:01
 **/
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Num138 {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // 使用Map存储原先链表和新链表节点
        // 映射关系为: 旧1 : 新1
        Map<Node,Node> nodeMap = new HashMap<>();
        // 遍历原链表，取出值构建新链表
        for (Node x = head;x != null;x = x.next) {
            Node node = new Node(x.val);
            nodeMap.put(x,node);
        }
        // 再次遍历原链表，将next和random赋值
        for (Node x = head;x != null;x = x.next) {
            // 因为旧节点和新节点是一一对应的关系
            // 因此 newNode.next就是old.next对应的节点
            nodeMap.get(x).next = nodeMap.get(x.next);
            nodeMap.get(x).random = nodeMap.get(x.random);
        }
        return nodeMap.get(head);
    }
}